class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    int n;
    void dfs(vector<string>& ans,int left,int right,vector<char>& chs){
        if(left == n && right == n){ //先考虑递归边界
            ans.emplace_back(chs.begin(),chs.end());//拷贝构造
        }
        if(left == right && left < n){ //只能加左括号
            chs.push_back('(');
            dfs(ans,left+1,right,chs);
            chs.pop_back();
        }else if(left > right){ // 既可以加左括号，也可以加右括号
            if(left<n){
                chs.push_back('(');
                dfs(ans,left+1,right,chs);
                chs.pop_back();
            }
            chs.push_back(')');
            dfs(ans,left,right+1,chs);
            chs.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        this->n = n;
        vector<string> ans;
        vector<char> chs;
        dfs(ans,0,0,chs);
        return ans;
    }
};